package com.tgy.algorithm.leetcode_hot_100;

import java.util.*;
import java.util.stream.Collectors;

/**
 *
 * https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 *
 * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
 *
 *
 * 示例 1:
 *
 * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 * 示例 2:
 *
 * 输入: strs = [""]
 * 输出: [[""]]
 * 示例 3:
 *
 * 输入: strs = ["a"]
 * 输出: [["a"]]
 */

class Solution002 {
    public List<List<String>> groupAnagrams(String[] strs) {

        Map<String, List<String>> map = new HashMap();
        for (String str : strs) {
            int[] cInts = new int[26];
            char[] chars = str.toCharArray();
            for (char aChar : chars) {
                cInts[aChar - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < cInts.length; i++) {
                if (cInts[i] > 0) {
                    char c = (char) ('a' + i);
                    sb.append(c);
                    sb.append(cInts[i]);
                }
            }
            String key = sb.toString();
            List<String> stringList = map.getOrDefault(key, new ArrayList<>());
            stringList.add(str);
            map.put(key, stringList);
        }

        List<List<String>> result = new ArrayList<>();
        map.values().forEach(val->{
            result.add(val);
        });
        return result;
    }

    public List<List<String>> groupAnagrams01(String[] strs) {

        HashMap<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            StringBuilder sb = new StringBuilder();
            for (char c : charArray) {
                sb.append(c);
            }
            String key = sb.toString();
            List<String> mapOrDefault = map.getOrDefault(key, new ArrayList<>());
            mapOrDefault.add(str);
            map.put(key, mapOrDefault);
        }

        List<List<String>> result = new ArrayList<>();

        map.values().forEach(val->{
            result.add(val);
        });

        return result;
    }
}

public class _002_49_字母异位词分组 {

    public static void main(String[] args) {
        Solution002 solution002 = new Solution002();
//        solution002.groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});
//        List<List<String>> lists = solution002.groupAnagrams(new String[]{"",""});
        List<List<String>> lists = solution002.groupAnagrams01(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});
        System.out.println(lists);
    }
}
